package LeetCode.month01.day28;

import java.util.Arrays;

public class No1385 {
    public static void main(String[] args) {
        System.out.println(findTheDistanceValue(new int[]{4,5,8},new int[]{10,9,1,8},2));
    }
    public static int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int res = 0;
        for (int a1 : arr1) {
            int index = Arrays.binarySearch(arr2,a1-d);//二分查找key值在数组中的下标，如果没找到，会返回-待插入位置-1
            if(index<0) index = -index-1;//第一个大于a1-d的下标

            if(index==arr2.length||arr2[index]>a1+d){
                res++;
            }
        }
        return res;
        
//        int m = arr1.length;
//        int n = arr2.length;
//        Arrays.sort(arr2);
//        int count = 0;
//        for (int i = 0; i < m; i++) {
//            int left=0,right=n-1;
//            boolean flag = true;
//            while(left<=right){
//                int mid = left+(right-left)/2;
//                if(Math.abs(arr1[i]-arr2[mid])<=d){
//                    flag = false;
//                    break;
//                }else if(arr2[mid]>arr1[i]){
//                    right = mid-1;
//                }else{
//                    left=mid+1;
//                }
//            }
//            if(flag) count++;
//        }
//        return count;
    }
}
